import { ListNode } from "../../const";

/**
 * @link https://leetcode.cn/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-interview-150
 */
function hasCycle(head: ListNode | null): boolean {
  return false;
}

/**
 * @link https://leetcode.cn/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150
 */
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let head = new ListNode(-1);
  let tmp1 = l1;
  let tmp2 = l2;
  let cmp = 0;
  let tmp = head;
  while (tmp1 || tmp2) {
    if (
      (tmp1?.val === undefined ? 0 : tmp1.val) +
        (tmp2?.val === undefined ? 0 : tmp2.val) +
        cmp >=
      10
    ) {
      if (head.val === -1) {
        head.val =
          (tmp1?.val === undefined ? 0 : tmp1.val) +
          (tmp2?.val === undefined ? 0 : tmp2.val) +
          cmp -
          10;
      } else {
        tmp.next = new ListNode(
          (tmp1?.val === undefined ? 0 : tmp1.val) +
            (tmp2?.val === undefined ? 0 : tmp2.val) +
            cmp -
            10
        );
        tmp = tmp.next;
      }
      cmp = 1;
    } else {
      if (head.val === -1) {
        head.val =
          (tmp1?.val === undefined ? 0 : tmp1.val) +
          (tmp2?.val === undefined ? 0 : tmp2.val) +
          cmp;
      } else {
        tmp.next = new ListNode(
          (tmp1?.val === undefined ? 0 : tmp1.val) +
            (tmp2?.val === undefined ? 0 : tmp2.val) +
            cmp
        );
        tmp = tmp.next;
      }
      cmp = 0;
    }
    console.log(tmp, cmp, head);

    tmp1 = tmp1?.next || null;
    tmp2 = tmp2?.next || null;
  }
  if (cmp) {
    tmp.next = new ListNode(1);
  }
  let n: ListNode | null = head;
  while (n) {
    console.log(n);
    if (n.next) n = n.next;
    else n = null;
  }
  return head;
}

/**
 * @link https://leetcode.cn/problems/merge-two-sorted-lists/?envType=study-plan-v2&envId=top-interview-150
 */
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  let n1 = list1;
  let n2 = list2;
  let head = new ListNode(-1);
  let tmp = head;
  while (n1 || n2) {
    if (n1 && n2) {
      if (n1.val >= n2.val) {
        tmp.next = new ListNode(n2.val);
        tmp = tmp.next;
        if (n2.next) n2 = n2.next;
        else n2 = null;
      } else {
        tmp.next = new ListNode(n1.val);
        tmp = tmp.next;
        if (n1.next) n1 = n1.next;
        else n1 = null;
      }
    } else {
      if (n1) {
        tmp.next = new ListNode(n1.val);
        tmp = tmp.next;
        if (n1.next) n1 = n1.next;
        else n1 = null;
      }
      if (n2) {
        tmp.next = new ListNode(n2.val);
        tmp = tmp.next;
        if (n2.next) n2 = n2.next;
        else n2 = null;
      }
    }
  }
  let n = head.next;
  while (n) {
    console.log(n);
    if (n.next) n = n.next;
    else n = null;
  }
  return head.next;
}

/**
 * @link https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=top-interview-150
 * Definition for ListNode.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     random: ListNode | null
 *     constructor(val?: number, next?: ListNode, random?: ListNode) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */

const getRandomIndex = (head: ListNode, target: ListNode | null) => {
  let tmp: ListNode | null = head;
  let count = 0;
  while (tmp) {
    if (tmp === target) return count;
    tmp = tmp.next;
    count++;
  }
  return -1;
};

function copyRandomList(head: ListNode | null): ListNode | null {
  if (!head) return head;
  let randomIndexList: number[] = [];
  let nodeList = [];
  let temp: ListNode | null = head;
  let resultHead = null;
  let resultTmp = null;
  while (temp) {
    if (!resultTmp) {
      resultTmp = new ListNode();
      resultHead = resultTmp;
      resultTmp.val = temp.val;
    } else {
      let n = new ListNode();
      n.val = temp.val;
      resultTmp.next = n;
      resultTmp = resultTmp.next;
    }
    randomIndexList.push(getRandomIndex(head, temp.random as ListNode | null));
    nodeList.push(resultTmp);
    temp = temp.next;
  }
  for (let i = 0; i < nodeList.length; i++) {
    if (randomIndexList[i] === -1) nodeList[i].random = null;
    else nodeList[i].random = nodeList[randomIndexList[i]];
  }
  return resultHead;
}

/**
 * @link https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150
 */
function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  // 最左边的前一个
  let prev = null;
  // 最右边的后一个
  let next = null;

  //   待旋转的链表
  let reverseHead = head;

  let tmp = head;
  let count = 1;
  while (tmp) {
    if (left === 1) {
      prev = null;
    }
    if (left - 1 === count) {
      prev = tmp;
      reverseHead = tmp.next;
    }
    if (right === count) {
      next = tmp.next;
      tmp.next = null;
      break;
    }
    tmp = tmp.next;
    count += 1;
  }
  let n = reverseHead;
  let nextNode = next;
  while (n) {
    let tmp = n.next;
    n.next = nextNode;
    nextNode = n;
    if (tmp) n = tmp;
    else break;
  }
  if (prev) {
    prev.next = n;
  } else {
    head = n;
  }
  return head;
}

/**
 * @link https://leetcode.cn/problems/remove-nth-ListNode-from-end-of-list/?envType=study-plan-v2&envId=top-interview-150
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let nodeList = [];
  if (!head) return head;
  let ListNode: ListNode | null = head;
  while (ListNode) {
    nodeList.push(ListNode);
    ListNode = ListNode.next;
  }
  if (nodeList.length - 1 - n < 0) {
    head =
      nodeList.length - 1 - n + 2 < nodeList.length
        ? nodeList[nodeList.length - 1 - n + 2]
        : null;
  } else {
    nodeList[nodeList.length - 1 - n].next =
      nodeList.length - 1 - n + 2 < nodeList.length
        ? nodeList[nodeList.length - 1 - n + 2]
        : null;
  }
  return head;
}

/**
 * @link https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/?envType=study-plan-v2&envId=top-interview-150
 */
function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (!head) return head;
  let st = [];
  let count = 0;
  let n: ListNode | null = head;
  while (n) {
    if (!st.length) {
      st.push(n);
      count += 1;
    } else {
      if (st[st.length - 1].val !== n.val) {
        if (count > 1) {
          while (count) {
            st.pop();
            count -= 1;
          }
          count += 1;
        }
        st.push(n);
      } else {
        st.push(n);
        count += 1;
      }
    }
    n = n.next;
  }
  if (count > 1) {
    while (count) {
      st.pop();
      count -= 1;
    }
  }
  for (let i = 0; i < st.length; i++) {
    st[i].next = i + 1 < st.length ? st[i + 1] : null;
  }

  return st[0] || null;
}

/**
 * @link https://leetcode.cn/problems/rotate-list/?envType=study-plan-v2&envId=top-interview-150
 */
function rotateRight(head: ListNode | null, k: number): ListNode | null {
  if (!head) return null;
  let n: ListNode | null = head;
  let count = 0;
  let prev: ListNode | null = head;
  while (n) {
    prev = n;
    n = n.next;
    count += 1;
  }
  prev.next = head;

  let tmp: ListNode | null = head;
  prev = head;
  while (count - k && tmp) {
    prev = tmp;
    tmp = tmp.next;
    console.log(prev, tmp);

    count -= 1;
  }
  prev && (prev.next = null);
  return tmp;
  // return ans;
}

/**
 * @link https://leetcode.cn/problems/partition-list/?envType=study-plan-v2&envId=top-interview-150
 */
function partition(head: ListNode | null, x: number): ListNode | null {
  let head1 = null;
  let head2 = null;
  let n = head;
  let tmp1 = null;
  let tmp2 = null;
  while (n) {
    console.log(n);
    if (n.val >= x) {
      if (!tmp2) {
        tmp2 = new ListNode(n.val);
        head2 = tmp2;
      } else {
        tmp2.next = new ListNode(n.val);
        tmp2 = tmp2.next;
      }
    } else {
      if (!tmp1) {
        tmp1 = new ListNode(n.val);
        head1 = tmp1;
      } else {
        tmp1.next = new ListNode(n.val);
        tmp1 = tmp1.next;
      }
    }
    n = n.next;
  }

  tmp1 ? (tmp1.next = head2) : (head1 = head2);
  return head1;
}

export default {
  hasCycle,
  addTwoNumbers,
  mergeTwoLists,
  reverseBetween,
  copyRandomList,
  removeNthFromEnd,
  deleteDuplicates,
  rotateRight,
  partition,
};
